import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;


public class APrioriBordersSets {
	
	static float[] percentageMinSups = { 0.4f , 0.5f , 0.6f , 0.7f , 0.8f , 0.9f};
	static int min_sup;
	static int[][] DATA;
	
	static final File pathToFolder = new File(System.getProperty("user.dir") + "/data/Session1");
	/************************/
	static ArrayList<ArrayList<ItemSet>> all_freq_itemsets = new ArrayList<ArrayList<ItemSet>>();
	/************************/
	static Map<String,ItemSet> border_minus = new TreeMap<String, ItemSet>();
	static Map<String, ItemSet> border_plus = new TreeMap<String, ItemSet>();	
	/************************/
	static ArrayList<ItemSet> closed_frequent_itemsets = new ArrayList<ItemSet>();	
	static ArrayList<ItemSet> free_frequent_itemsets = new ArrayList<ItemSet>();	
	
	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		long startTime;
		long endTime;
		
		// Read all Files from Dictonary
		for (final File fileEntry : pathToFolder.listFiles()) {
		
			if (!fileEntry.getName().endsWith(".csv"))	
				continue;
			
			for(float percentageMinSup : percentageMinSups) {
				startTime = System.currentTimeMillis();
				
		        System.out.println(fileEntry.getName() + " with a minSupport of " + (percentageMinSup) +" ...");
		        
				// Clear DataStore
				DATA = null; 
				all_freq_itemsets.clear();
				border_minus.clear();
				border_plus.clear();
				closed_frequent_itemsets.clear();
				free_frequent_itemsets.clear();
				
				DATA = APrioriBordersSets.getInput(fileEntry.getAbsolutePath());
				
				// Calc Frequent Cut
				min_sup = (int)Math.ceil(DATA[0].length * percentageMinSup);
				
				// APriori berechnen
				ArrayList<ItemSet> currentItemSetArray = initializeFirstFrequentItemSets();
				// Es wird solange gejoint, bis keine größeren Frequent ItemSets mehr gebildet werden können.
				while (!currentItemSetArray.isEmpty()) {
					currentItemSetArray = joinItemSets(currentItemSetArray);
				}
				
				// Closed Itemsets berechnen
				calcClosedItemSets();
				
				// Free ItemSets berechnen
				calcFreeItemSets();
				
				File outputFile = new File(pathToFolder.getAbsolutePath() + "/" + fileEntry.getName()+"_APriori_" + percentageMinSup + ".txt");//"_log" + System.currentTimeMillis() + ".txt");
		        BufferedWriter aprioriOutput = new BufferedWriter(new FileWriter(outputFile));
		        
				printBasicApriori(aprioriOutput);
				aprioriOutput.close();
				
				outputFile = new File(pathToFolder.getAbsolutePath() + "/" + fileEntry.getName()+"_Borders_" + percentageMinSup + ".txt");//"_log" + System.currentTimeMillis() + ".txt");
				BufferedWriter borderOutput = new BufferedWriter(new FileWriter(outputFile));
		        
				printBorders(borderOutput);
				borderOutput.close();
				
				outputFile = new File(pathToFolder.getAbsolutePath() + "/" + fileEntry.getName()+"_Closed_" + percentageMinSup + ".txt");//"_log" + System.currentTimeMillis() + ".txt");
				BufferedWriter closedOutput = new BufferedWriter(new FileWriter(outputFile));
		        
				printClosedFree(closedOutput);
				closedOutput.close();
				
				endTime = System.currentTimeMillis();
				System.out.println("Calculated in " + (endTime-startTime) + "ms.");
			}
	    }
	}
	
	private static void printBorders(BufferedWriter output) throws IOException {
		// Print all Borders Summary
		output.write("Border Plus: " + border_plus.size());
		output.newLine();
		output.write("Border Minus: " + border_minus.size());
		output.newLine();
		output.write("---------------");		
		output.newLine();
		// Border Plus
		output.write("Border Plus:");
		output.newLine();
		for(Entry<String, ItemSet> data : border_plus.entrySet()) {
			for(int items : data.getValue().items) {
				output.write(items + " ");
			}
			output.newLine();
		}
		output.write("---------------");
		output.newLine();
		// Border Minus
		output.write("Border Minus:");
		output.newLine();
		for(Entry<String, ItemSet> data : border_minus.entrySet()) {
			for(int items : data.getValue().items) {
				output.write(items + " ");
			}
			output.newLine();
		}
	}

	private static void printClosedFree(BufferedWriter output) throws IOException {
		// Print all Closed Summary
		output.write("Closed: " + closed_frequent_itemsets.size());
		output.newLine();
		output.write("Free: " + free_frequent_itemsets.size());
		output.newLine();
		output.write("---------------");		
		output.newLine();
		// Closed
		output.write("Closed:");
		output.newLine();
		for(ItemSet data : closed_frequent_itemsets) {
			for(int items : data.items) {
				output.write(items + " ");
			}
			output.newLine();
		}
		output.write("---------------");
		output.newLine();
		// Free
		output.write("Free:");
		output.newLine();
		for(ItemSet data : free_frequent_itemsets) {
			for(int items : data.items) {
				output.write(items + " ");
			}
			output.newLine();
		}
	}
	
	private static void printBasicApriori(BufferedWriter output) throws IOException {
		// Print all FrequentItemSets Summary
		int countAll = 0;
		for(int row = 0; row < all_freq_itemsets.size(); row++){
			output.write("ItemSet-"+(row+1)+" ("+all_freq_itemsets.get(row).size()+"); ");
			output.newLine();
			countAll += all_freq_itemsets.get(row).size();
		}
		output.write("---------------");
		output.newLine();
		output.write("= " + countAll);
		output.newLine();
		output.newLine();
		
		// Print all FrequentItemSets
		for(int row = 0; row < all_freq_itemsets.size(); row++){
			output.write("ItemSet-"+(row+1)+" ("+all_freq_itemsets.get(row).size()+"): ");
			output.newLine();
			for(int col = 0; col < all_freq_itemsets.get(row).size(); col++){
				for (int item = 0; item < all_freq_itemsets.get(row).get(col).items.length; item++){
					output.write((all_freq_itemsets.get(row).get(col).items[item]) + "; ");
				}
				output.newLine();
			}
			output.newLine();
		}
		
	}

	private static int[][] getInput(String FILEPATH) throws IOException {
		int[][] DATA;
		BufferedReader reader = 
                new BufferedReader(new FileReader(FILEPATH));
        
        String input = reader.readLine();
        int numItems = input.split(",").length;
        int numTransactions = 1;
        while( (input = reader.readLine()) != null ) {
        	numTransactions++;
        }

        DATA = new int[numTransactions][numItems];
                
        reader.close();
        reader = new BufferedReader(new FileReader(FILEPATH));
        
        int count = 0;
        
        while( (input = reader.readLine()) != null ) {
        	String[] tmp_s = input.split(",");
        	int[] tmp_i = new int[tmp_s.length];
        	for(int i = 0; i < tmp_s.length; i++){
        		tmp_i[i] = Integer.parseInt(tmp_s[i]);
        	}
        	DATA[count] = tmp_i;
        	count++;
        }
        reader.close();

        int[][] transponsedDATA = new int[numItems][numTransactions];
        
        // transpose
        if (DATA.length > 0) {
            for (int i = 0; i < DATA[0].length; i++) {
                for (int j = 0; j < DATA.length; j++) {
                    transponsedDATA[i][j] = DATA[j][i];
                }
            }
        }
        return transponsedDATA;
    }
	
	private static ArrayList<ItemSet> initializeFirstFrequentItemSets()
	{
		ArrayList<ItemSet> oneElementItemSet = new ArrayList<ItemSet>();
		
		for (int t = 0; t < DATA.length; t++) {
			int count = 0;
			for (int i = 0; i < DATA[0].length; i++) {
				if (DATA[t][i] == 1)
					count++;
			}
			
			ItemSet itemSet = new ItemSet();
			itemSet.items = new int[1];
			itemSet.items[0] = t;
			itemSet.count = count;
			oneElementItemSet.add(itemSet);			
		}
		oneElementItemSet = getFrequentItemSets(oneElementItemSet);
		all_freq_itemsets.add(oneElementItemSet);
		return oneElementItemSet;
	}
	
	private static ArrayList<ItemSet> getFrequentItemSets(ArrayList<ItemSet> itemSets)
	{
		ArrayList<ItemSet> goodItemSets = new ArrayList<ItemSet>();
		
		for (ItemSet itemSet : itemSets) {
			if (itemSet.count >= min_sup)
			{
				goodItemSets.add(itemSet);
			}
			
			calcBorderPlus(itemSet);
		}
		
		return goodItemSets;
	}

	private static void calcBorderPlus(ItemSet itemSet) 
	{
		// Check if itemset is frequent
		if (itemSet.count >= min_sup)
		{				
			// Check if itemSet has more than one item
			if (itemSet.items.length > 1)
			{
				// Generate all ItemSets with k-1 items
				ArrayList<ItemSet> parentItemSets = new ArrayList<ItemSet>();
				for (int i = 0; i < itemSet.size(); i++) {
					ItemSet parentItemSet = new ItemSet();
					parentItemSet.items = new int[itemSet.items.length - 1];
					
					for (int j = i; j < itemSet.size() + i - 1; j++)
					{
						parentItemSet.setItem(j - i, itemSet.getItem(j % itemSet.size()));
					}						
					parentItemSets.add(parentItemSet);
				}
				
				for (ItemSet parentItemSet : parentItemSets) {
					
					StringBuilder builderFirst = new StringBuilder();
					for (int i = 0; i < DATA.length; i++) {
						Boolean contains = false;
						for (int j = 0; j < parentItemSet.items.length; j++) {
							if (parentItemSet.items[j] == i)
							{
								contains = true;
								break;
							}
						}
						builderFirst.append(contains ? "1" : "0");
					}
					
					border_plus.remove(builderFirst.toString());
				}
			}
			
			// create key
			StringBuilder builderNewBigItemSet = new StringBuilder();
			for (int i = 0; i < DATA.length; i++) {
				Boolean contains = false;
				for (int j = 0; j < itemSet.items.length; j++) {
					if (itemSet.items[j] == i)
					{
						contains = true;
						break;
					}
				}
				builderNewBigItemSet.append(contains ? "1" : "0");
			}
			
			border_plus.put(builderNewBigItemSet.toString(), itemSet);
		}
		else
		{
			// create key
			StringBuilder builderNewBigItemSet = new StringBuilder();
			for (int i = 0; i < DATA.length; i++) {
				Boolean contains = false;
				for (int j = 0; j < itemSet.items.length; j++) {
					if (itemSet.items[j] == i)
					{
						contains = true;
						break;
					}
				}
				builderNewBigItemSet.append(contains ? "1" : "0");
			}
			// Add item that not reach the min support
			border_minus.put(builderNewBigItemSet.toString(), itemSet);
		}
	}	
	
	private static void calcClosedItemSets()
	{
		if (all_freq_itemsets.size() > 0)
		{
			ArrayList<ItemSet> currentItemSets = new ArrayList<ItemSet>();
			ArrayList<ItemSet> superSets = new ArrayList<ItemSet>();
						
			for (int i = 0; i < all_freq_itemsets.size() - 1; i++) 
			{
				currentItemSets.clear();
				superSets.clear();
				
				currentItemSets.addAll(all_freq_itemsets.get(i));
				superSets.addAll(all_freq_itemsets.get(i + 1));
				
				for (ItemSet currentItemSet : currentItemSets) 
				{
					boolean contains = false;
					for (ItemSet superSet : superSets) 
					{
						contains = currentItemSet.count == superSet.count && contains(superSet.items, currentItemSet.items);
						
						if (contains)
							break;
					}
					
					if (!contains)
					{
						closed_frequent_itemsets.add(currentItemSet);
					}
				}
			}
			
			// Die Frequent Itemsets mit dem meisten Items haben nur SuperSets mit Support 0.
			closed_frequent_itemsets.addAll(all_freq_itemsets.get(all_freq_itemsets.size() - 1));
		}
	}
	
	private static void calcFreeItemSets()
	{
		if (all_freq_itemsets.size() > 0)
		{
			ArrayList<ItemSet> currentItemSets = new ArrayList<ItemSet>();
			ArrayList<ItemSet> subSets = new ArrayList<ItemSet>();
						
			for (int i = all_freq_itemsets.size() - 1; i > 0; i--) 
			{
				currentItemSets.clear();
				subSets.clear();
				
				currentItemSets.addAll(all_freq_itemsets.get(i));
				subSets.addAll(all_freq_itemsets.get(i - 1));
				
				for (ItemSet currentItemSet : currentItemSets) 
				{
					boolean allSubSetAreMoreSupported = false;
					for (ItemSet subSet : subSets) 
					{
						if (!contains(currentItemSet.items, subSet.items))
							continue;
						
						allSubSetAreMoreSupported = currentItemSet.count < subSet.count;
						
						if (!allSubSetAreMoreSupported)
							break;
					}
					
					if (allSubSetAreMoreSupported)
					{
						free_frequent_itemsets.add(currentItemSet);
					}
				}
			}
			
			// Gibt es einelementrige Itemset, die von allen Transaktionen gekauft wurden, sind diese auch free.
			for (ItemSet itemSetOneItem : all_freq_itemsets.get(0)) 
			{
				if (itemSetOneItem.count == DATA[0].length)
				{
					free_frequent_itemsets.add(itemSetOneItem);
				}
			}
		}
	}
	
	private static boolean contains(final int[] outer, final int[] inner) 
	{		
		boolean contains = false;
	    for (int i = 0; i < inner.length; i++) 
	    {
			for (int j = 0; j < outer.length; j++) 
			{
				if (outer[j] == inner[i])
				{
					contains = true;
					break;
				}
				contains = false;
			}
			
			if (!contains)
				return false;
		}
	    
	    return contains;
	}
	
	public static ArrayList<ItemSet> joinItemSets(ArrayList<ItemSet> freq_itemsets)
	{
		// Hier werden alle Kandidaten ItemSets gepseichert.
		ArrayList<ItemSet> newItemSets = new ArrayList<ItemSet>();
				
		// Vergleiche alle ItemSets miteinander, ob sie gejoint werden d�rfen.
		for (ItemSet itemSetFirst : freq_itemsets) {
			for (ItemSet itemSetSecond : freq_itemsets) {
				Boolean isValid = false;
				for(int t = 0; t < itemSetSecond.items.length; t++)
				{
					// Es müssen alle item Gleich sein bis auf das letzte
					if (t < itemSetSecond.items.length -1 &&
							itemSetFirst.items[t] == itemSetSecond.items[t])
						continue;
					// Das letzte Item des ersten ItemSets muss kleiner als das letzte Item des zweiten Itemsets
					else if (t == itemSetSecond.items.length -1 
							&& itemSetFirst.items[t] < itemSetSecond.items[t]) 
					{
						isValid = true;
					}	
					break;
				}
				
				// Dürfen sie gejoint werden, nimm alle Elemente aus dem ersten ItemSet und das letzte auch dem zweiten.
				if (isValid)
				{
					ItemSet itemSetNew = new ItemSet();
					itemSetNew.items = new int[itemSetSecond.items.length + 1];
					for(int r = 0; r < itemSetFirst.items.length; r++)
					{
						itemSetNew.items[r] = itemSetFirst.items[r];
					}
					itemSetNew.items[itemSetSecond.items.length] = itemSetSecond.items[itemSetSecond.items.length - 1];
					
					int countFrequency = 0;
					
					// Nimm das erste Item, aus dem neuen ItemSet. Laufe nun �ber alle Eintr�ge.
					for(int z = 0; z < DATA[itemSetNew.items[0]].length; z++)
					{
						// Ist ein Eintrag 1, dann pr�fe, ob alle anderen Items an der gleichen Stelle auch eine 1 haben.
						// 0 Das erste Item in dem neuen ItemSet
						// z ist der Kunde in dem Item
						if (DATA[itemSetNew.items[0]][z] == 1)
						{
							boolean canCount = true;
							for(int p = 0; p < itemSetNew.items.length; p++)
							{
								if (DATA[itemSetNew.items[p]][z] != 1)
								{
									canCount = false;
									break;
								}
							}
							
							if (canCount) countFrequency++;
						}
					}
					
					itemSetNew.count = countFrequency;	
					newItemSets.add(itemSetNew);
				}
			}
		}
		//select frequent itemsets and add to all frequent itemsets
		ArrayList<ItemSet> frequent_itemsets = getFrequentItemSets(newItemSets);
		if (!frequent_itemsets.isEmpty())
			all_freq_itemsets.add(frequent_itemsets);
		
		return frequent_itemsets;
	}	
}
